//
// Created by Administrator on 2024/6/18.
//
#include "SeqList.h"

/**
 * 初始化表
 * @param list
 */
void SeqInitList(SeqList *list)
{
    list->base = (ElemType *) malloc(sizeof(ElemType) * SEQLiST_INIT_SIZE);
    assert(list->base != NULL);
    list->capacity = SEQLiST_INIT_SIZE;
    list->size = 0;
}

/**
 * 容量扩充
 * @param list
 * @return
 */
bool seq_inc(SeqList *list)
{
    ElemType *newBase = (ElemType *) realloc(list->base, sizeof(ElemType) * (list->capacity + INC_SIZE));
    if (newBase == NULL)
    {
        printf("incremnet space error,because out of memory .\n");
        return FALSE;
    }
    list->base = newBase;
    list->capacity += INC_SIZE;
    return TRUE;
}

/**
 * 尾插入法
 * @param list
 * @param x
 */
void seq_push_back(SeqList *list, ElemType x)
{
    //Check whether the sequential table space is full and whether the space increase fails
    if (list->size >= list->capacity && !seq_inc(list))
    {
        printf("sequential table space is full,and can not insert data at the end  %d. \n", x);
    }
    //data tail insert data
    list->base[list->size] = x;
    list->size++;
}

/**
 * 头插入法
 * @param list
 * @param x
 */
void seq_push_front(SeqList *list, ElemType x)
{
    if (list->size >= list->capacity && !seq_inc(list))
    {
        printf("sequential table space is full,and can not to insert data in the header %d. \n", x);
    }
    //Move the sequential table data back
    for (int i = list->size; i > 0; i--)
    {
        list->base[i] = list->base[i - 1];
    }
    //data insert the sequential table's head
    list->base[0] = x;
    list->size++;
}


/**
 * 打印
 * @param list
 */
void seq_show_list(SeqList *list)
{
    for (int i = 0; i < list->size; i++)
    {
        printf("%d ", list->base[i]);
    }
    printf("\n");
}

/**
 * 尾删除法
 * @param list
 */
void seq_pop_back(SeqList *list)
{
    if (list->size == 0)
    {
        printf("the sequential table is empty,and can not be deleted");
        return;
    }
    //the sequential table's size-1 and to achieve the purpose of deletion
    list->size--;
}

/**
 * 头删除法
 * @param list
 */
void  seq_pop_front(SeqList *list)
{
    if (list->size == 0)
    {
        printf("the sequential table is empty,and can not be deleted");
        return;
    }
    for (int i = 0; i < list->size - 1; ++i)
    {
        list->base[i] = list->base[i + 1];
    }
    list->size--;
}

//按位置插入数据
void seq_insert_pos(SeqList *list, int pos, ElemType x)
{
    if (pos < 0 || pos > list->size)
    {
        printf("the insertion data location is illegal,and the data can not be inserted . \n");
        return;
    }
    if (list->size >= list->capacity && !seq_inc(list))
    {
        printf("sequential table space is full,and can not to insert data in the header %d. \n", x);
    }
    //Move the sequential table data back
    for (int i = list->size; i > pos; i--)
    {
        list->base[i] = list->base[i - 1];
    }
    list->base[pos] = x;
    list->size++;
}

//查找数据
int seq_find(SeqList *list, ElemType key)
{
    if (list->size == 0)
    {
        printf("the sequential table is empty,and can not be found");
        return -1;
    }
    for (int i = 0; i < list->size; ++i)
    {
        if (list->base[i] == key)
        {
            return i;
        }
    }
    return 0;
}

//求长度
int seq_length(SeqList *list)
{
    return list->size;
}

//按位置删除数据
void seq_delete_pos(SeqList *list, int pos)
{
    //datemine whether the data is legitimate
    if (pos < 0 || pos > list->size)
    {
        printf("the insertion data location is illegal,and the data can not be deleted . \n");
        return;
    }
    for (int i = pos; i < list->size - 1; ++i)
    {
        list->base[i] = list->base[i + 1];
    }
    list->size--;
}

//按值删除数据
void seq_delete_val(SeqList *list, ElemType key)
{
    int pos = seq_find(list, key);
    if (pos == -1)
    {
        printf("the data to be deleted does not exist . \n");
        return;
    }
    seq_delete_pos(list, pos);
}

//顺序 冒泡排序
void seq_sort(SeqList *list)
{
    for (int i = 0; i < list->size - 1; ++i)
    {
        for (int j = 0; j < list->size - i - 1; ++j)
        {
            if (list->base[j] > list->base[j + 1])
            {
                ElemType tmp = list->base[j];
                list->base[j] = list->base[j + 1];
                list->base[j + 1] = tmp;
            }
        }
    }
}

//逆序
void seq_resver(SeqList *list)
{
    if(list->size==0||list->size==1){
        return;
    }
    int low=0;
    int high=list->size-1;
    ElemType tmp;
    while(low<high){
        tmp=list->base[low];
        list->base[low]=list->base[high];
        list->base[high]=tmp;
        low++;
        high--;
    }
}

//清空
void seq_destroy(SeqList *list){
    free(list->base);
    list->base=NULL;
    list->capacity=0;
    list->size=0;
}

//合并
//将两个从小到大排序的有序表按照由小到大的顺序合并到另一个有序表中
void seq_merge(SeqList *lt, SeqList *la, SeqList *lb)
{
    //构造存放有序表la和lb的有序表lt
    lt->capacity = la->size + lb->size;
    lt->base = (ElemType*)malloc(sizeof(ElemType)*lt->capacity);
    assert(lt->base != NULL);

    int ia = 0;
    int ib = 0;
    int ic = 0;
    //当有序表la和lb中的元素都还没比较完时，将它们相应下标下的元素进行比较，并将小的元素放入lt
    while(ia<la->size && ib<lb->size)
    {
        if(la->base[ia] < lb->base[ib])
            lt->base[ic++] = la->base[ia++];
        else
            lt->base[ic++] = lb->base[ib++];
    }
    //当只有有序表la中有元素时，将la中的剩余元素逐一放入lt
    while(ia < la->size)
    {
        lt->base[ic++] = la->base[ia++];
    }
    //当只有有序表lb中有元素时，将lb中的剩余元素逐一放入lt
    while(ib < lb->size)
    {
        lt->base[ic++] = lb->base[ib++];
    }
    //更新有序表lt的长度
    lt->size = la->size + lb->size;
}
